package com.shiguiwu.springmybatis.algorithm.search;

/**
 * @description: 插值查找算法
 * 此算法改进二分查询
 * 使用min的值，自适应mid的值，不在写死int mid = (low+high)/2
 * 公式 int mid =  left + (findVal - arr[left]) / (arr[right] - arr[left]) * (right - left);
 * @author: stone
 * @date: Created by 2022/11/16 22:13
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.search
 */
public class InsertValSearch extends AbstractSearch implements Search{

    public InsertValSearch(int[] arrays) {
        super(arrays);
    }

    @Override
    public int search(int value) {
        return this.insertValSearch(0, this.arrays.length - 1, value, this.arrays);
    }



    @Override
    public int[] searchArrays(int value) {
        return new int[0];
    }

    /**
     * 插值查找算法
     * @param left 左边
     * @param right 右边
     * @param findVal 查找值
     * @param arr 数组
     * @return 找到的索引
     */
    private int insertValSearch(int left, int right,int findVal, int[] arr) {
        //防止数组越界和分母为0
        if (left >= right || findVal < arr[left] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        //查询mid的值
        int mid = left + (findVal - arr[left]) / (arr[right] - arr[left]) * (right - left);
        int midVal = arr[mid];

        if (midVal > findVal) {
            return insertValSearch(left, mid - 1, findVal, arr);
        }

        else if (midVal < findVal) {
            return insertValSearch(mid + 1, right, findVal, arr);
        }

        else {
            return mid;
        }


    }
}
